The present invention relates generally to classification of sections of software by matching the usage background of the section to a usage profile derived by earlier profiling of the software.
Fueled by the growing importance of the Internet, interest in the area of distributed systems (two or more computers connected by a communications medium) has increased in recent years. Programmers desiring to take advantage of distributed systems modify existing application programs to perform on distributed systems, or design applications for placement on distributed systems.
A distributed application is an application containing interconnected application units (xe2x80x9cunitsxe2x80x9d) that are placed on more than one computer in a distributed system. By placing units on more than one computer in a distributed system, a distributed application can exploit the capabilities of the distributed system to share information and resources, and to increase application reliability and system extensibility. Further, a distributed application can efficiently utilize the varying resources of the computers in a distributed system.
Various types of modular software, including software designed in an object-oriented framework, can conceivably be distributed throughout a distributed system. Object-oriented programming models, such as the Microsoft Component Object Model (xe2x80x9cCOMxe2x80x9d), define a standard structure of software objects that can be interconnected and collectively assembled into an application (which, being assembled from component objects, is herein referred to as a xe2x80x9ccomponent applicationxe2x80x9d). The objects are hosted in an execution environment created by system services, such as the object execution environments provided by COM. This system exposes services for use by component application objects in the form of application programming interfaces (xe2x80x9cAPIsxe2x80x9d), system-provided objects and system-defined object interfaces. Distributed object systems such as Microsoft Corporation""s Distributed Component Object Model (DCOM) and the Object Management Group""s Common Object Request Broker Architecture (CORBA) provide system services that support execution of distributed applications.
In accordance with object-oriented programming principles, the component application is a collection of object classes which each model real world or abstract items by combining data to represent the item""s properties with functions to represent the item""s functionality. More specifically, an object is an instance of a programmer-defined type referred to as a class, which exhibits the characteristics of data encapsulation, polymorphism and inheritance. Data encapsulation refers to the combining of data (also referred to as properties of an object) with methods that operate on the data (also referred to as member functions of an object) into a unitary software component (i.e., the object), such that the object hides its internal composition, structure and operation and exposes its functionality to client programs that utilize the object only through one or more interfaces. An interface of the object is a group of semantically related member functions of the object. In other words, the client programs do not access the object""s data directly, but instead call functions on the object""s interfaces to operate on the data. Polymorphism refers to the ability to view (i.e., interact with) two similar objects through a common interface, thereby eliminating the need to differentiate between two objects. Inheritance refers to the derivation of different classes of objects from a base class, where the derived classes inherit the properties and characteristics of the base class.
An application containing easily identifiable and separable units is more easily distributed throughout a distributed system. One way to identify separable units is to describe such units with structural metadata about the units. Metadata is data that describes other data. In this context, structural metadata is data describing the structure of application units. Further, application units are desirably location-transparent for in-process, cross-process, and cross-computer communications. In other words, it is desirable for communications between application units to abstract away location of application units. This flexibly enables the distribution of application units.
The partitioning and distribution of applications are problematic and complicated by many factors.
To partition an application for distribution, a programmer typically determines a plan for distributing units of the application based on past experience, intuition, or data gathered from a prototype application. The application""s design is then tailored to the selected distribution plan. Even if the programmer selects a distribution plan that is optimal for a particular computer network, the present-day distribution plan might be rendered obsolete by changes in network topology. Moreover, assumptions used in choosing the distribution plan might later prove to be incorrect, resulting in an application poorly matched to its intended environment.
Generally, to distribute an application, one can work externally or internally relative to the application. External distribution mechanisms work without any modification of the application and include network file systems and remote windowing systems on a distributed system. Although external distribution mechanisms are easy to use and flexible, they often engender burdensome transfers of data between nodes of the distributed system, and for this reason are far from optimal. Internal distribution mechanisms typically modify the application to be distributed in various ways. Internal distribution mechanisms allow optimized application-specific distribution, but frequently entail an inordinate amount of extra programmer effort to find an improved distribution and modify the application. Further, internal systems frequently provide ad hoc, one-time results that are tied to the performance of a particular network at a particular time.
An automatic distributed partitioning system (ADPS) works internally relative to an application to partition application units, and works automatically or semi-automatically to save programmer effort in designing distributed applications.
In the 1970""s, researchers postulated that the best way to create a distributed application was to use a compiler in a run time environment to partition the application, and to provide the exact same code base to each of plural distributed machines as used on a single machine to execute the distributed application. After analyzing the structure of procedures and parameters in the source code of an application, metadata describing the structure of an application were generated from the application source code. Using this metadata, these ADPSs profiled the application and generated a communication model for the application. The Interconnected Processor System (ICOPS) is an example of an ADPS designed in the 1970""s. The Configurable Applications for Graphics Employing Satellites (CAGES) also supported creation of distributed applications, but did not support automatic application profiling at all. A more recent example of an ADPS is the Intelligent Dynamic Application Partitioning (IDAP) System. ICOPS, CAGES, and IDAP suffer from numerous drawbacks relating to the universality, efficiency, and automation of these systems.
ICOPS, CAGES, and IDAP use static-type classification to partition an application and distribute it through a distributed computing environment. ICOPS and CAGES partition and distribute static functions and data such as application procedures using classification based upon the structure of the static functions and data. IDAP partitions and distributes statically allocated components using classification based upon the static type of the components. Static-type classification is inadequate for classifying application units that are dynamically instantiated and destroyed throughout execution, such as those designed according to COM and other object-oriented programming models. Deterioration of static-type classification is especially pronounced when application execution is data or input driven.
Dynamically allocated memory is memory that is allocated to specific uses as needed, without specifying how much memory is needed in advance. When memory is no longer needed for the specific use, it is freed for later allocation to other uses. The process of freeing memory can be costly where it involves searching memory for program segments or data that are no longer active. A dynamically allocated object is an object for which space is allocated in memory as needed.
Dynamic classification has found limited application in the field of dynamically allocated memory. Lifetime prediction techniques dynamically classify an object to predict the behavior of the object. In memory management systems using memory heaps, a heap can become fragmented if long-lived and short-lived program segments are randomly allocated from the same heap. Memory heap fragmentation can be minimized if objects with short lifetimes are allocated memory from a separate heap. A process known as xe2x80x9cgarbage collectionxe2x80x9d identifies memory that is no longer needed, and frees such memory. Garbage collection is more efficient if dynamically allocated objects are grouped with objects having similar lifetimes. Lifetime prediction can reduce memory overhead and improve reference locality.
One technique for predicting lifetime of a dynamically allocated object uses a stack pointer at the time the object is dynamically allocated to identify the object. This technique is highly dependent on processor architecture. Another technique uses a hashed value of the return addresses from each of the invocation frames in a call stack to identify an object. Because this technique traverses the call stack accessing invocation frames, it is called a procedure call chain (PCC). The depth to which the call stack is traversed can vary. A depth-n PCC consists of the return addresses from each of the top n invocation frames. In general, the accuracy of a lifetime prediction increases with the depth of the PCC. This technique lacks sufficient contextual information to dynamically classify an object in an object-oriented system. PCCs form a sparse, one-dimensional space: the range of valid return addresses. Object-oriented programming adds a second dimension: the identity of the object executing the code. Dynamic memory allocation techniques limit contextual information in order to speed up the process of dynamic classification. None of these techniques for predicting lifetime of dynamically allocated objects utilizes available contextual information about the dynamically allocated objects themselves. Specifically, none utilizes identity of dynamically allocated objects for dynamic classification.
The present invention pertains to classification of a section of software by matching the usage background of the section to a usage profile determined by previous profiling software. As software executes, a dynamic structure tracks the usage of sections of the software and provides state information used to create the usage profile and usage background. Software executes under expected usage conditions, generating a usage profile. The usage profile includes information about the identity of a section being profiled and the usage of other sections of the software preceding the usage of the section being profiled. A section map includes a mapping of the usage profile to an outcome for the usage profile. When the software executes again, a usage background includes information about the identity of a section being classified and the usage of other section of the software leading up to the usage of a section being classified. In the section map, the usage background is matched to the usage profile most similar to it. The outcome that is mapped to the matched usage profile is followed.
According to an illustrated embodiment of the present invention, the sections of software are application units. The application executes in one or more profiling scenarios, generating usage profiles. These usage profiles map to locations in a distributed computing environment. During execution of the application outside of the profiling scenarios, a usage background includes information about an application unit and the preceding usage of application units. After matching the usage background to a usage profile in the unit map, a unit instantiates at the appropriate location in the distributed computing environment.
A usage profile can correspond to the usage of a single section of software in a single profiling scenario. Alternatively, a usage profile can correspond to the usage of multiple sections of software in a single profiling scenario, or the usage of multiple sections of software across multiple profiling scenarios.
The usage profile and usage background include information about the identity of a section of software being profiled or classified and the preceding usage of other sections. The identity information is an identifier for a group to which the section belongs. Alternatively, the identity information is an identifier for an individual section assigned by an operating system or by an instrumentation system.
Information about the preceding usage of other sections includes identity information for preceding sections. For example, a call chain records the identities of sections called leading up to the section being profiled or classified. Alternatively, information about the preceding usage of other sections can include identifiers of functions used by preceding sections. For example, instead of or in addition to the section identity call chain, a call chain can record the return addresses of functions used leading up to the section being profiled or classified. A call chain can include various subsets of section identities and function identifiers to enable varying levels of precision in dynamic classification. For example, a call chain can include only an identifier from the section immediately preceding the section being classified. In the illustrated embodiment, a usage profile and usage background can be a table entry including the identifier of a unit creating the unit being profiled or classified. Alternatively, the table entry can include a description of the function called to create the unit being profiled or classified.
A dynamic structure tracks the usage of sections preceding the section being profiled or classified. The dynamic structure tracks sections and/or functions used before the section being classified. Instead of a single dynamic structure, multiple dynamic structures can be used. For example, in the illustrated embodiment, a call stack tracks function calls while a separate stack tracks unit identities.
The outcome that is mapped to a usage profile corresponds to an event that occurs when a usage background matches a usage profile. In the illustrated embodiment, an outcome is a location in a distributed computing environment for an application unit to be instantiated. Alternatively, the dynamic classification techniques of the present invention can be applied to lifetime prediction for memory heap management, garbage collection, load balancing among resources, cache management, or other applications in which sections of software are profiled then classified to optimize performance.
Additional features and advantages of the present invention will be made apparent from the following detailed description of an illustrated embodiment, which proceeds with reference to the accompanying drawings.